<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
	<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=utf-8">
	<TITLE></TITLE>
	<META NAME="GENERATOR" CONTENT="OpenOffice.org 2.0  (Linux)">
	<META NAME="CREATED" CONTENT="20061002;10362900">
	<META NAME="CHANGED" CONTENT="20061002;14121400">
	<STYLE TYPE="text/css">
	<!--
		@page { size: 21cm 29.7cm; margin: 2cm }
		P { margin-bottom: 0.21cm }
	-->
	</STYLE>
</HEAD>
<BODY LANG="es-AR" DIR="LTR">
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><FONT SIZE=4 STYLE="font-size: 16pt"><U><B>Informe
sistemas operativos.</B></U></FONT></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>Integrantes</B>:</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"> 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Rodrigo Carreras
(rcarreras86@gmail.com)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Franco Pellegrini
(frapell@gmail.com)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Matias C&oacute;rdoba
(cormatias@gmail.com)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"> <B>Grupo</B>: 08</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"> <B>Fecha de Entrega:</B>
2 de Octubre de 2006</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm; page-break-before: always">
<BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><FONT SIZE=4 STYLE="font-size: 16pt"><U><B>Introducci&oacute;n</B></U></FONT></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">En este informe se podr&aacute;
observar como se implementaron m&uacute;ltiples Threads, que permiten
que se puedan dividir los trabajos de un proceso en varios mas
livianos.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se ver&aacute; como es el
uso de los mismo, a trav&eacute;s de dos ejemplos, TABLE y ENV. El el
primero tendremos un ejemplo de productor-consumidor, en donde se
implementan MUTEX y SEMAFOROS para el control de regiones cr&iacute;ticas,
y variables compartidas. El segundo es un ejemplo de un diccionario,
el en cual hay dos grupos de hilos, los que leen y los que escriben.
Tambi&eacute;n se detallara de que forma se solucionaron los
problemas que generaron la incorporaci&oacute;n forzosa de los
pthreads. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"> 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm; page-break-before: always">
<FONT SIZE=4><U><B>I. Table</B></U></FONT></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">A continuaci&oacute;n se
detallara de que forma fue implementado el programa TABLE. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Este es un ejemplo de
Productor-Consumidor, en donde existen pthreads que son encargados de
ingresar elementos a la tabla, es decir entradas (Productor) y los
que se encargan de extraer las entradas antes mencionadas
(Consumidor). 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La base de la aplicaci&oacute;n
brindada por la c&aacute;tedra, estaba preparada para trabajar con un
solo proceso, lo que hac&iacute;a que el trabajo no se repartiera, y
se hiciera por consiguiente de forma secuencial. El trabajo
consisti&oacute;,  entonces, en aplicar pthreads, es decir procesos
livianos, que permitieran una ejecuci&oacute;n no secuencial.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Cuando se implementaron
hilos, aparecieron diversos problemas, que proven&iacute;an de los
elementos que compart&iacute;an los procesos livianos. Es decir, nos
encontr&aacute;bamos ante &quot;condiciones de carreras&quot;,
asignaciones corruptas, etc. Para solucionar estos problemas que
surg&iacute;an, se implement&oacute; una estructura de control que
permiti&oacute; proteger las &quot;regiones criticas&quot;. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La estructura elegida
fueron los MUTEX (Mutual Exclusion) acompa&ntilde;ados del uso de
SEMAFOROS.  Los primeros, permiten que las sentencias que se
encuentren protegidas no se vean afectadas por condiciones de
carrera, y los segundos, controlan la cantidad de veces que se
ejecuta cierto procedimiento, en este caso, controla que no siga
escribiendo una vez que la tabla ya este llena, o que no la lea si
&eacute;sta est&aacute; vac&iacute;a.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Cabe aclarar que se
incorpor&oacute; la compilaci&oacute;n condicional, que permite
obtener dos programas (el mismo, uno con fallas y el otro no). 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">#ifdef __DEBUG 
//Compilaci&oacute;n condicional.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">#endif 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para poder realizar esto
es necesario definir o no la constante __DEBUG, que se encuentra en
table.h</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Los m&oacute;dulos
brindados por la c&aacute;tedra fueron: 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">table_test: es el
	modulo de ejecuci&oacute;n en donde se encuentra la funciones de
	inicio y finalizaci&oacute;n de la aplicaci&oacute;n. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">table: es el
	encargado de definir la estructura en donde se almacenan y extraen
	los datos. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">yield: contiene
	funciones que contribuyen a que exista un mayor interleaving entre
	los procesos. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">randomize: contiene
	funciones encargadas de generar n&uacute;meros aleatorios.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Como se mencion&oacute;
anteriormente, algunos de &eacute;stos, fueron modificados para poder
implementar m&uacute;ltiples pthreads. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Los cambios realizados se
mencionan a continuaci&oacute;n:</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><U><B>I.I.I En
table_test.c</B></U></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Fue alterado para poder
dividir el &uacute;nico proceso en ejecuci&oacute;n en varios
procesos livianos. Para ello fue implementada la librer&iacute;a:</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">&lt;pthread.h&gt;
	&Eacute;sta contiene funciones que permiten crear, manipular y
	destruir los threads. Adem&aacute;s, posee estructuras para
	controlarlos. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">&lt;semaphore.h&gt;
	Es la librer&iacute;a encargada de proporcionar funciones y
	procedimientos para la manipulaci&oacute;n de los sem&aacute;foros.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se crearon dos funciones
aqu&iacute;, que son las encargadas de ejecutar la &quot;producci&oacute;n&quot;
y &quot;consumos&quot; de los elementos que se encuentran en la
tabla. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Ellas son: 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">table_read: Es un
procedimiento que se encarga de &quot;consumir&quot; (leer) datos
ingresados en la tabla. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">table_write: a diferencia
de read, se encarga de &quot;producir&quot; (escribir) datos en la
tabla.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Adem&aacute;s se
implementaron bucles en el main principal, que tiene CONSTANTES
asociadas. Estos permiten crear y destruir m&uacute;ltiples hilos,
con solo modificar los valores de las CONSTANTES (HILO_READ,
HILO_WRITE.)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><U><B>I.I.II En table.c</B></U></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se modificaron algunas de
las funciones internas para poder implementar los MUTEX, que permiten
proteger las regiones criticas que aqu&iacute; se encuentran, y los
SEM&Aacute;FOROS. Adem&aacute;s se implemento una funci&oacute;n
table_getted, que engloba dos de table.c. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Las modificaciones
mencionadas, se comentan mas abajo, ya que fueron hechas para poder
mantener el programa, es decir, proteger las &quot;Regiones
Criticas&quot;. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><B><U>I.II Problemas
surgidos durante la ejecuci&oacute;n.</U></B> 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Al dividir un proceso en
m&uacute;ltiples procesos livianos, nos encontramos ante condiciones
de carrera, que provocaban que los elementos que se compart&iacute;an
no cumplieran los pre y post condiciones adecuadas. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Dichos inconvenientes se
ve&iacute;an por medio de las Asserciones que estaban implementadas
para hacer cumplir las condiciones antes mencionadas. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para poder atacar estos
problemas, realizamos un estudio del c&oacute;digo, a fin de ver las
&quot;regiones criticas&quot;, las cuales deb&iacute;amos proteger.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm; page-break-before: always">
A continuaci&oacute;n se enumera una lista de los problemas
encontrados. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B><SPAN STYLE="text-decoration: none">1)
</SPAN></B>C&oacute;digo extra&iacute;do de la funci&oacute;n
table_alloc: 
</P>
<TABLE WIDTH=100% BORDER=1 BORDERCOLOR="#000000" CELLPADDING=4 CELLSPACING=0>
	<COL WIDTH=256*>
	<THEAD>
		<TR>
			<TD WIDTH=100% VALIGN=TOP>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>unsigned
				int</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>table_alloc(table
				t, object *o) </I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>{</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	bool
				found = false;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	unsigned
				int i = 0;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#ff0000">assert(t!=NULL);</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT COLOR="#ff0000"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	assert(t-&gt;_table!=NULL);</I></FONT></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT COLOR="#ff0000"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	assert(o!=NULL);</I></FONT></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	yield();</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	i
				= 0;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#008000">#ifdef
				__DEBUG</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#eb613d">sem_wait(&amp;(t-&gt;vacio));</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#008000">#endif</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	while
				(!found &amp;&amp; i&lt;table_size(t)) </I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	{</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		<FONT COLOR="#008000">#ifdef
				__DEBUG</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		<FONT COLOR="#eb613d">pthread_mutex_lock(&amp;(t-&gt;mutex));</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		<FONT COLOR="#008000">#endif</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		if
				(t-&gt;_table[i]==NULL) </I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		{</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			(t-&gt;_table)[i]
				= o;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			found
				= true;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		}
				</I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		else
				</I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><I><FONT SIZE=2 STYLE="font-size: 11pt">		{</FONT></I></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			i++;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		}</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		if
				(found) </I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		{</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			t-&gt;_allocated++;</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			yield();</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			<FONT COLOR="#ff0000">assert(table_allocated(t)&lt;=table_size(t));/**/</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			<FONT COLOR="#008000">#ifdef
				__DEBUG</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			<FONT COLOR="#eb613d">pthread_mutex_unlock(&amp;(t-&gt;mutex));</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT COLOR="#eb613d"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			sem_post(&amp;(t-&gt;lleno));</I></FONT></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			<FONT COLOR="#008000">#endif</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			return(i);</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		}
				</I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		else
				</I></FONT>
				</P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		{</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			<FONT COLOR="#008000">#ifdef
				__DEBUG</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			<FONT COLOR="#eb613d">pthread_mutex_unlock(&amp;(t-&gt;mutex));</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		<FONT COLOR="#008000">	#endif</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>			</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>		}</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	}</I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#008000">#ifdef
				__DEBUG</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#eb613d">sem_post(&amp;(t-&gt;lleno));</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	<FONT COLOR="#008000">#endif</FONT></I></FONT></P>
				<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><FONT SIZE=2 STYLE="font-size: 11pt"><I>	return(table_size(t));</I></FONT></P>
				<P ALIGN=JUSTIFY><FONT SIZE=2 STYLE="font-size: 11pt"><I>}</I></FONT></P>
			</TD>
		</TR>
	</THEAD>
</TABLE>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Una vez implementando los
pthread, uno de los problemas que exist&iacute;a era que el tama&ntilde;o
de elementos allocados en la tabla era mayor que los elementos de la
tabla. Este hecho no debe ocurrir, ya que no pueden existir m&aacute;s
elementos guardados en la tabla que los lugares que &eacute;sta
dispone. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Este error se ve&iacute;a
evidenciado por la siguiente aserci&oacute;n. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	<I><FONT SIZE=2 STYLE="font-size: 11pt">assert(table_allocated(t)&lt;=table_size(t))</FONT></I></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Esto era posible ya que
al existir dos o m&aacute;s procesos que est&aacute;n ingresando
valores a la tabla, incrementa el valor de las allocaciones antes de
llegar al assert. Esto permite que haya mas  de las posibles en la
tabla. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para solucionar este
problema implementamos exclusi&oacute;n mutua para hacer que las
sentencias abarcadas por los MUTEX, fueran at&oacute;micas.  En el
c&oacute;digo 1) muestra las sentencias abarcadas por estos. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Una de las posibles
ejecuciones que llevan a que la cantidad de allocaciones no sea
correcta es:</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea A=WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea B=WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea N el tama&ntilde;o de
la tabla y k un &iacute;ndice, 0&lt;=k&lt;N</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">A se ejecuta y
	encuentra que el lugar k de la tabla es vac&iacute;o. Cuando est&aacute;
	por escribir en este lugar el Scheduler cede el procesador a B.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">B se ejecuta y
	encuentra que puede escribir en el lugar k de la tabla. Se termina
	de ejecutar, por consiguiente escribe en k, y aumenta la variable
	que cuenta los lugares allocados. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">A se termina de
	ejecutar y escribe nuevamente en k, y aumenta los lugares allocados.
		</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">En esta ejecuci&oacute;n
se muestra como falla el assert antes mencionado. Esta es la
justificaci&oacute;n de por qu&eacute; se coloco exclusi&oacute;n
mutua en dicha parte del programa.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>2) </B>C&oacute;digo
extra&iacute;do de table_getted</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">bool</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">table_getted (table tbl,
int idx)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">{</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	sem_wait(&amp;(tbl-&gt;lleno));</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	pthread_mutex_lock(&amp;tbl-&gt;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#endif</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	if (table_is_def(tbl,
idx)) 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	{</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		yield();</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		table_release(tbl,
idx);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		#ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		pthread_mutex_unlock(&amp;tbl-&gt;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		sem_post(&amp;(tbl-&gt;vacio));</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		#endif 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		return (1);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	}</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	pthread_mutex_unlock(&amp;tbl-&gt;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	sem_post(&amp;(tbl-&gt;vacio));</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#endif</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	return (0);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">}</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Hay que aclarar dos
modificaciones importantes que se realizaron en esta parte del
programa. 
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se cre&oacute; la
	funci&oacute;n table_getted, que es la encargada de llamar a
	table_is_def y table_relase. Fue necesaria crearla, ya que era
	preciso introducir un MUTEX que las englobara  y SEM&Aacute;FOROS
	para evitar que existan tablas llenas. Si esto no se hiciera se
	caeria en una ejecuci&oacute;n fallida incorrecta. Un ejemplo de
	esto se muestra mas abajo. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La incorporaci&oacute;n
	del MUTEX.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La incorporaci&oacute;n
	de los SEMAFOROS.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Una posible ejecuci&oacute;n
de la aplicaci&oacute;n es la que se menciona a continuaci&oacute;n.
En esta se evidencia  la necesidad de crear una nueva funci&oacute;n
y de aplicar exclusi&oacute;n mutua para solucionarlo. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Ejemplo.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea A = READ</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea B = WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea el tama&ntilde;o de
la tabla = N</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">supongamos ahora que
	B escaneaba la tabla y encuentra que el primer lugar vac&iacute;o es
	k, con 0&lt;k&lt;N. B no escribe ning&uacute;n valor en el lugar k
	aun. el scheduler le cede el procesador a A. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">A quiere leer el
	valor que se encuentra en el lugar k de la tabla.  luego este llama
	a table_getted, que a su vez llama a table_is_def. esta funci&oacute;n
	le devolver&aacute; un valor que indicara que es posible leer ese
	valor, es decir que es table.k!=NULL. Luego se llama a
	table_release, que sera la encargada de leer el valor de la posici&oacute;n
	k. Antes de leer el valor el scheduler cede el procesador a B.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">B hace los mismos
	pasos que A, solo que el scheduler lo detiene antes de la siguiente
	asserci&oacute;n &lt;assert(t-&gt;_table!=NULL);&gt; que se
	encuentra en table_release. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Luego A se termina
	de ejecutar y table.k==NULL.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">el Scheduler cede el
	procesador a B, que ejecuta la asserci&oacute;n, y por consiguiente
	falla. 
	</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Colocando MUTEX en estas
dos regiones logramos solucionar el problema antes mencionado.</P>
<OL START=5>
	<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"></P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">3)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La ejecuci&oacute;n que
se ilustra a continuaci&oacute;n muestra la necesidad de implementar
sem&aacute;foros para evitar tablas llenas.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea  A=READ</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea  B=WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea N=tama&ntilde;o de la
tabla.</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se ejecuta B N veces
	sin que el scheduler le ceda el procesador a A. Luego obtenemos una
	tabla llena.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Mediante la
implementaci&oacute;n de los sem&aacute;foros esto no puede suceder
ya que cuando existe una tabla llena, el proceso B se va a dormir,
generando que se ejecute A.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">De manera an&aacute;loga,
si tenemos una tabla que posee K entradas, y A se ejecuta K veces. A
se encontrara con una tabla vac&iacute;a para leer. Nuevamente con el
uso de los sem&aacute;foros, tenemos cuando la tabla est&aacute;
vac&iacute;a se env&iacute;a a dormir al proceso A.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Hay que aclarar que
incorporar la estructura de sem&aacute;foros puede ocurrir un
problema llamado “inanici&oacute;n” que se da cuando todos los
procesos se van a dormir y no hay posibilidad de despertar a ninguno.
Esto concluye en que el programa no finalice su ejecuci&oacute;n.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La inanici&oacute;n no
puede darse en este caso ya que cuando un proceso lee de la tabla
lleva a que se le de la posibilidad de escribir a otro proceso en la
misma. Por lo que en todo momento existe uno o mas hilos activos. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"> 
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><U><B>I. III Problemas</B></U></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Existe el inconveniente
de que cuando se crea una cantidad grande de hilos (mas de 350
aproximadamente), el programa se muestra inestable y suele dar fallos
de segmentaci&oacute;n cuando se realizan los thread_join. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Adem&aacute;s dependiendo
de la ejecuci&oacute;n se observan la presencia de Memory Leak, que
son generados por el procedimiento phread_create. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm; page-break-before: always">
<FONT SIZE=4><U><B>II. ENV</B></U></FONT></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">A continuaci&oacute;n se
detallar&aacute; de que forma fue implementado el programa ENV. &Eacute;ste
consiste en un diccionario, que almacena palabras y definiciones
varias. Esa informaci&oacute;n es almacenada en un tipo especial de
datos llamado “&Aacute;rbol Rojo y Negro”. &Eacute;stos son
arboles binarios que cumplen ciertas propiedades que garantizan que
sean balanceados, por ende que su b&uacute;squeda sea del  O(log(n)).</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">El trabajo con este
programa consisti&oacute; en hacer que su proceso principal se
dividiera en mutiles threads, para poder brindar mejoras de
eficiencia. Al estar preparado para trabajar con un s&oacute;lo
proceso, surgieron inconvenientes al incorporar los hilos, estos
derivaban de condiciones de carrera,  lo que provocaba que no se
pudieran mantener las pre y post condiciones de los procedimientos y
funciones del programa.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para proteger las
“Regiones Criticas” se recurri&oacute; a la utilizaci&oacute;n de
MUTEX.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Fue incorporada la
compilaci&oacute;n condicional, que permite obtener dos programas (el
mismo, uno con fallas y el otro no). 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">#ifdef __DEBUG 
//Compilaci&oacute;n condicional.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">#endif 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para poder realizar esto
es necesario definir o no la constante __DEBUG, que se encuentra en
rbtree.h</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Los m&oacute;dulos
brindados por la c&aacute;tedra fueron:</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>env_test</B>: Es
	el modulo encargado de la ejecuci&oacute;n principal, es aqu&iacute;
	en donde se divide el proceso de ejecuci&oacute;n en varios procesos
	livianos.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>env</B>: Es el
	modulo en donde se encuentra la estructura diccionario y funciones, 
	procedimientos encargado de manipularla. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>ieentry</B>: es
	un tipo de “Nodo” que se usa para las hojas del &aacute;rbol.
	Posee esta estructura y funciones para manipularlas. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>rbtree</B>:
	Estructura &Aacute;rbol Rojo y Negro, que es la encargada de
	almacenar las palabras. Posee funciones y procedimientos para
	manipular dicha estructura.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>randomize</B>:
	Modulo generador de n&uacute;meros aleatorios.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>yield</B>: M&oacute;dulo
	encargado de ceder el procesador a otro proceso.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se realizaron
modificaciones en algunos de los m&oacute;dulos mencionados, para
poder obtener una ejecuci&oacute;n multi hilo y adem&aacute;s poder
mantenerla. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">las modificaciones
realizadas fueron: 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><U><B>II.I.I En env_test</B></U></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Es en donde se encontraba
el proceso principal. Por ello aqu&iacute; es en donde se crean los
m&uacute;ltiples hilos. Al igual que en TABLE, se implementaron
bucles que permiten obtener pthread con solo modificar los valores de
unas contantes. Los nombres de estas son: HILO_READ, HILO_WRITE.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para poder implementar
los Threads y los MUTEX fue necesario agregar la librer&iacute;a
&lt;pthread.h&gt;, la cual conten&iacute;a las funciones y
procedimientos necesarios para manipularlos.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se agregaron a su vez dos
funciones m&aacute;s, llamadas: 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>env_read</B>:
	&Eacute;ste procedimiento se encarga de leer los valores almacenados
	en el diccionario. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><B>env_write</B>:
	&Eacute;ste procedimiento se encarga de escribir valores en el
	diccionario. Si los valores ya est&aacute;n escritos los
	sobreescribe.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><U><B>II.I.II En rbtree</B></U></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Aqu&iacute; es en donde
se implementaron los MUTEX para proteger las regiones cr&iacute;ticas.
Las funciones modificadas fueron <SPAN STYLE="font-weight: medium"><I>rbtinsert</I></SPAN>
y <I>rbtget</I>. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">A continuaci&oacute;n se
enuncian qu&eacute; problemas surg&iacute;an y de qu&eacute; forma se
solucionaron los mismo. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">1) Funci&oacute;n
rbtinsert</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">struct rbtree*
rbtinsert(struct rbtree* este, alfa *a)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">{	</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    #ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">   
pthread_mutex_lock(&amp;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    #endif</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    __rbtassert(este);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    este =
__rbtinsert(este, a);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    yield0();</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    este -&gt; color =
negro;</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    #ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">   
pthread_mutex_unlock(&amp;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    #endif</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    return este;</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">}</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Los problemas que
surg&iacute;an, si no se colocaban los mutex en estos lugares eran
varios y proven&iacute;an de las condiciones de carrera que se
establec&iacute;an entre los diversos hilos que corr&iacute;an.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Antes de ir a los
ejemplos de posibles ejecuciones fallidas, vamos a hacer una rese&ntilde;a
de la forma de inserci&oacute;n que lleva a cabo el algoritmo de
rbtree.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">La funci&oacute;n
insertar es recursiva, por lo que hace llamadas a si misma. Esta se
encarga de crear un nodo e insertarlo en la rama correcta del &aacute;rbol.
Luego de hacer esto prosigue un proceso de recoloreo del mismo. Si
esto es interrumpido o incorrecto se puede obtener un &aacute;rbol
que no cumple las especificaciones de un rbtree. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Adem&aacute;s cabe
aclarar que las asserciones fueron implementadas por medio de una
funci&oacute;n creada en el TAD, por lo que sus sentencias son no
at&oacute;micas. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Ahora vamos a los
ejemplos que muestran posibles ejecuciones que llevan a una
inconsistencia en la estructura.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">1)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea A=WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea B=WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">supongamos que:</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Se ejecuta el
	proceso A y crea el nuevo nodo. Identifica en qu&eacute; rama del
	&aacute;rbol lo debe insertar, y lo inserta. 
	</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">El Scheduler cede el
	procesador a B. Este se ejecuta y antes de realizar un inserci&oacute;n
	verifica (por medio de la funci&oacute;n __rbtassert) que la
	estructura del &aacute;rbol sea correcta. Luego al no haber
	terminado A es muy posible que las condiciones del &aacute;rbol sean
	incorrectas. 
	</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para solucionar este
problema fue necesario hacer que la funci&oacute;n de inserci&oacute;n
no tuviera interrupciones, ya que &eacute;stas llevan a que la
estructura del &aacute;rbol no sea la correcta. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Por &eacute;ste motivo se
implement&oacute; MUTEX en la funci&oacute;n mencionada. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">2) C&oacute;digo extra&iacute;do
de  rbtget y __rbtassert.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">int rbtget(const struct
rbtree* este, alfa* a, alfa* res)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">{</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    int caso;</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	pthread_mutex_lock(&amp;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#endif</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">    __rbtassert(este);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#ifdef __DEBUG</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	pthread_mutex_unlock(&amp;mutex);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	#endif</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	...</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">return 0;</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">}</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">void __rbtassert(const
struct rbtree* este)</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">{</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	if (este) {</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		assert(este-&gt;color==negro
|| 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">			((!este-&gt;left ||
este-&gt;left-&gt;color==negro) 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">				&amp;&amp;
(!este-&gt;right || este-&gt;right-&gt;color==negro)));</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		__rbtassert(este-&gt;left);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">		__rbtassert(este-&gt;right);</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">	}</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">}</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Como se mencion&oacute;
anteriormente el control de que la estructura del &aacute;rbol sea
correcto se lleva a cabo a trav&eacute;s de la funci&oacute;n
recursiva __rbtassert(este); Esta puede ser interrumpida durante su
ejecuci&oacute;n, lo que puede llevar  a problemas de control.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Una posible ejecuci&oacute;n
fallida derivada por esto seria:</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea A = WRITE</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">sea B = READ</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Supongamos que se ejecuta
B.  &Eacute;ste antes de leer un dato chequea que las propiedades del
&aacute;rbol se cumplan, es decir que posea la correcta coloraci&oacute;n.
Para ello llama a la funci&oacute;n __rbtassert. &Eacute;sta se
ejecuta, pero no finaliza, es decir se detiene a la mitad de la
ejecuci&oacute;n del assert que posee. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">El scheduler cede el
procesador a A. &Eacute;ste se ejecuta y finaliza correctamente. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">El scheduler cede el
procesador a B. &Eacute;ste falla ya que las condiciones del &aacute;rbol
cambiaron al insertar un nuevo elemento. Hay que aclarar que no en
todo momento esto puede fallar, pero existen ejecuciones que s&iacute;
lo hacen.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Por este motivo fue
necesario colocar en rbtget un MUTEX que hace que al llamar a
__rbtassert no tenga interrupciones.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm"><U><B>II.II Problemas</B></U></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Luego de correr Valgrind,
obtubimos que dependiendo de la ejecuci&oacute;n y el numero de hilos
creados existen Memory Leak, que provienen del procedimiento
pthread_create.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=LEFT STYLE="margin-bottom: 0cm; page-break-before: always"><FONT SIZE=4><U><B>III.
Herramientas utilizadas.</B></U></FONT></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Para llevar a cabo los
programas finales usamos las siguientes aplicaciones: 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<OL>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><I>Kate</I>: para la
	edici&oacute;n de los c&oacute;digos.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><I>Gcc</I>: GNU
	project C compiler. Para la compilaci&oacute;n de los proyectos.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><I>Valgrind</I>:
	Usada para el rastreo de memory leak.</P>
	<LI><P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><I>make</I>: Usada
	para la compilaci&oacute;n autom&aacute;tica de las aplicaciones.</P>
</OL>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Los programas fueron
corridos en los siguientes sistemas operativos: KUBUNTU 6.06, DEBIAN
testing y DEBIAN sarge.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=CENTER STYLE="margin-bottom: 0cm; page-break-before: always">
<FONT SIZE=4><U><B>Conclusi&oacute;n</B></U></FONT></P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Haber trabajado en este
proyecto nos brindo un panorama amplio y preciso acerca de como se
manejan los procesos en nuestro sistema operativo, a si mismo, de que
forma hace para repartir los recursos que son limitados como el
microprocesador.</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm">Podemos concluir diciendo
que implementar pthreads, es un m&eacute;todo que puede lograr gran
eficiencia, siempre y cuando se haya tenido en cuenta el cuidado de
las regiones cr&iacute;ticas, variables, recursos compartidos, etc. 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"> 
</P>
<P ALIGN=JUSTIFY STYLE="margin-bottom: 0cm"><BR>
</P>
</BODY>
</HTML>